#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

string LCS(string s1, string s2){
	int M = s1.size()+1;
	int N= s2.size()+1;
	vector<int> S(M*N);
	vector<char> C(M*N);

	C[0] = 0;
	for(int j=0; j<N; j++)
		S[j] = 0;

	for(int j=0; j<M; j++)
		S[j*N] = 0;

	for(int i=1;i<M;i++){
		for(int j=1; j<N; j++){
			if(s1[i-1] == s2[j-1]){
				S[i*N+j] = S[(i-1)*N+j-1]+1;
				C[i*N+j] = 'e';
			}else{
				S[i*N+j] = max(S[i*N+j-1],S[(i-1)*N+j]);
				C[i*N+j] = S[i*N+j-1] > S[(i-1)*N+j] ? 'd' : 'u';
			}
		}
	}

	stack<char> s;

	for(int i=M-1, j=N-1; i&&j ; ){
		char path = C[i*N+j];
		if(path == 'e'){
			i--;
			j--;
			s.push(s2[j]);
		}else if(path == 'd'){
			j--;
		}else if(path == 'u'){
			i--;
		}	
	}

	string result;
	while(!s.empty()){
		result += s.top();
		s.pop();
	}
	return result;
}


void main(){
	cout<<LCS("abdfbeeeeeeeeee","abcbdabfe")<<endl;
}
